Multithreading environments allow different parts of a process, known as threads, to execute concurrently. Multithreading processes may be carefully designed so that multiple threads can execute concurrently without interfering with each other unnecessarily.
In multiprocessor computer systems, threads may run in parallel on the processors that form the multiprocessor computer system. Moreover, if a program can be broken down into constituent threads, such computer systems can run the program more quickly since concurrently running threads of the same program may execute in parallel. Single processor, multitasking computer systems can also execute multiple threads of execution virtually simultaneously through the use of various resource scheduling mechanisms well known to those skilled in the art.
When multithreading programs are object-oriented, each thread of a program may independently invoke methods of objects. However, because of software constraints in the program or hardware constraints in the computer system, only a predefined number of threads may be allowed to invoke the methods of any given object at one time.
For example, an object may contain a method that accesses a shared computer resource, such as an I/O device, that can only handle one access at a time. Since concurrently running threads may concurrently seek to invoke that method of the object, access to that method of the object must be restricted to one thread at a time. When execution of a method is restricted in this manner, the object of which this method is a member is said to be "synchronized" with the thread that currently has access to the method.
In the past, various approaches have been used to synchronize an object with a thread. These include the use of synchronization constructs like mutexes, monitors, and semaphores. One approach for the management of synchronization constructs, the dynamic-association approach, is described in U.S. patent application Ser. No. 08/569,805, entitled "OBJECT SYNCHRONIZATION MODULE AND METHOD WITH REDUCED MEMORY REQUIREMENTS", filed by Timothy G. Lindholm and Jonathan Payne on Dec. 8, 1995 (attorney docket No. A-62531).
In the dynamic-association approach, synchronization constructs are associated with and disassociated with objects as needed. For example, during runtime, a thread may invoke a method of an object that requires synchronization. A synchronization construct is associated with the object if a synchronization construct has not already been associated with the object. When the thread exits the method that required synchronization of the thread with the object, and there are no other threads currently requiring synchronization with the object, the synchronization construct is disassociated with the object.
Synchronization constructs may be stored in a data structure referred to as a synchronization construct cache. Managing the association of these synchronization constructs with objects involves the use of other data structures which are also part of, or associated with, the synchronization construct cache. A hash table links an object to its associated synchronization construct. A free list contains entries identifying the synchronization constructs that are not currently associated with any object.
The operations involved in managing the association of synchronization constructs with objects require the use of data structures (i.e. the hash table, synchronization construct, and free list) that are part of the synchronization construct cache. Because the synchronization construct cache is shared by all threads, the data structure representing the synchronization construct cache is a global data structure. A reference or an update to a data structure in the synchronization construct cache may require a lock of the global data structure representing the synchronization construct cache to prevent interference to and from other concurrently executing threads that may also desire to access the data structure. A lock of a global data structure is herein referred to as a global lock. Because the synchronization construct cache is a global data structure, it may be referred to as the global synchronization construct cache.
A thread contending for a data structure globally locked by another thread is delayed until the other thread releases its global lock. Delays such as this one, which are caused by one thread contending for a data structure locked by another thread, are herein referred to as contention delays. As threads executing in a computer system increase the number of operations performed on global data structures, or the number of threads increases, contention delays can often increase to undesirable levels.
Based on the foregoing, it clearly desirable to overcome the problems associated with the prior art.